package com.zzg.datastructure.tree.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * @Author zhengzg
 * @Date 2022-09-28
 * @Version v1.0
 * 堆排序
 */
public class HeapSort {

    public static void main(String[] args) {
        //要求将数组进行升序排序
        // int[] arr = {4, 6, 8, 5, 9};
        // 创建要给 80000 个的随机的数组
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000);
            // 生成一个[0, 8000000) 数
        }

        System.out.println("排序前");

        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是=" + date1Str);

        heapSort(arr);

        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序后的时间是=" + date2Str);

        //System.out.println("排序后=" + Arrays.toString(arr));
    }

    // 堆排序方法
    public static void heapSort(int[] arr) {
        int temp = 0;
        System.out.println("堆排序");
        // 将无序列构建成一个堆，根据升序还是降序选择大顶堆和小顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        /*
         * 1.将堆顶元素与末尾元素交换，将最大元素沉到数据末尾
         * 2.重新调整结构，使其满足堆定义，然后继续交换栈顶元素与当前末尾元素，反复执行调整+交换步骤，直到数组有序
         */
        for (int i = arr.length - 1; i > 0; i--) {
            // 交换
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }

    }

    /**
     * 调整为大顶堆
     *
     * @param arr    待传入的数组
     * @param i      表示非叶子节结点在数组中的索引
     * @param length 表示对多少个元素继续调整，length是在逐渐的减少
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        // 先取出当前元素的值，保存在临时变量
        int temp = arr[i];
        // 开始调整
        // k = i * 2 + 1 => k是i的左子节点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // 说明左子节点小于右子节点的值
            // k + 1 < length 保证右子节点在数据长度范围内
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            // 如果子节点大于父节点的值
            if (arr[k] > temp) {
                // 把较大的值赋给当前结点
                arr[i] = arr[k];
                // i 指向 k，继续循环比较
                i = k;
            } else {
                break;
            }
        }
        // 当for循环结束的时候，我们已经将以i为父节点的树的最大值，放在了最顶（局部）
        // 此时i是最底部子结点，temp为最小值，在for循环中最大值已经被赋予在最开始的i的位置
        arr[i] = temp;
    }

}
